package summer.graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Solution1466 {
    public int minReorder(int n, int[][] connections) {
        List<List<int[]>> edges = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            edges.add(new ArrayList<>());
        }
        for (int[] x : connections) {
            edges.get(x[0]).add(new int[]{x[1], 1});
            edges.get(x[1]).add(new int[]{x[0], 0});
        }
        boolean[] visited = new boolean[n];
        LinkedList<Integer> queue = new LinkedList<>();
        queue.add(0);
        int res = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                int cur = queue.removeFirst();
                visited[cur] = true;
                List<int[]> edge = edges.get(cur);
                for (int[] x : edge) {
                    if (!visited[x[0]]) {
                        queue.add(x[0]);
                        if (x[1] == 1) res++;
                    }
                }
            }
        }
        return res;
    }
}
